import java.lang.*;
import java.util.*;

/**
 * Binary Search Tree Implementation.
 * No Duplicates allowed.
 **/

public class BinarySearchTree {

	private Node root = null;

	private class Node {
		Integer value = null;
		Node parent = null;
		Node left = null;
		Node right = null;
		Node(Integer val) {
			value = val;
		}
	}

	private void add(Integer ele){
		if(root == null) root = new Node(ele); else insert(ele, root);

	}

	private void insert(Integer val, Node start) {
		if(start.value < val) {
			if(start.right != null) {
				insert(val,start.right);
			}else{
				start.right = new Node(val);
				start.right.parent = start;
			}
		}

		if(start.value > val) {
			if(start.left != null) {
				insert(val,start.left);
			}else{
				start.left = new Node(val);
				start.left.parent = start;
			}
		}
	}

	private void print(Node start) {
		if(start != null && start.value != null) {
			System.out.println(start.value);
			print(start.left);
			print(start.right);
		}
	}

	private void printAll() {
		print(root);
	}

	int tempCount = 0;
	Integer xLargest = null;

	private void printSorted(Node start, int pos) {
		if(start != null){
			if(start.right != null) {
				printSorted(start.right, pos);
			}
			if(pos == ++tempCount){
				xLargest = start.value;
			}
			System.out.println(tempCount + "\t" + start.value);
			if(start.left != null){
				printSorted(start.left, pos);
			}
		}
	}

	public static void main(String[] args){
		if(args.length != 2) {
			throw new IllegalArgumentException("Provide value for k, the k(th) largest element in the Binary Tree AND Number of elements to be generated.");
		}

		int index = -1;
		int noOfEle = -1;

		try {
			index = Integer.parseInt(args[0]);
			noOfEle = Integer.parseInt(args[1]);
			if (index < 1) {
				throw new IllegalArgumentException("Index cannot be less than 1");
			}
			if(noOfEle < 1){
				throw new IllegalArgumentException("Number of elements for Binary Search Tree should be greater than 0.");
			}
		}catch (Exception e){
			throw new IllegalArgumentException("Illegal Argument. Could not parse the argumrnt to type integer.");
		}


		BinarySearchTree bst = new BinarySearchTree();
		Random rnd = new Random(4);
		System.out.println("Numbers are added in order:");
		for(int k = 0; k < noOfEle; ++k) {
			int toAdd = k;//rnd.nextInt(noOfEle)*rnd.nextInt(noOfEle*10)*rnd.nextInt(noOfEle);
			System.out.println((k+1) + "\t-->\t" + toAdd);
			bst.add(toAdd);
		}	       
		System.out.println("------Printing Sorted Value------");

		bst.printSorted(bst.root,Integer.parseInt(args[0]));
		if(bst.xLargest != null)
			System.out.println(args[0] + " largest value is: " + bst.xLargest) ;
		else
			System.out.println("Provided index value is more than the number of elements in Binary Search Tree.");
	}
}
